package leetcode;

/**
 * 32   最长有效括号
 * 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
 * <p>
 * 示例 1:
 * <p>
 * 输入: "(()"
 * 输出: 2
 * 解释: 最长有效括号子串为 "()"
 * 示例 2:
 * <p>
 * 输入: ")()())"
 * 输出: 4
 * 解释: 最长有效括号子串为 "()()"
 * <p>
 * <p>
 * 解题思路
 * 1，动态规划
 * 2，正向逆向结合
 * 3，栈
 *
 * @author: cuihao
 * @create: 2020-07-17 02:25
 **/
public class LongestValidParentheses {

    /**
     * 动态规划 推荐
     * <p>
     * // 公式
     * // dp[i] 表示 已 i结尾的有效长度
     * <p>
     * // if s[i] = ")" && s[i-1] = "("
     * // then: dp[i] = dp[i-2] + 2
     * <p>
     * // if s[i] = ")" && s[i-1] = ")" && s[i - dp[i-1] - 1] = "("
     * // then dp[i] = dp[i-1] + dp[i- dp[i-1] -2] + 2
     *
     * @param s
     * @return
     */
    public int dongtaiguihua(String s) {
        int maxans = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    dp[i] = (i >= 2
                            ? dp[i - 2]
                            : 0)
                            + 2;
                } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                    dp[i] = dp[i - 1]
                            + ((i - dp[i - 1]) >= 2
                                ? dp[i - dp[i - 1] - 2]
                                : 0)
                            + 2;
                }
                maxans = Math.max(maxans, dp[i]);
            }
        }
        return maxans;
    }

    /**
     * 正逆向结合
     *
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {

        if (s == null || s.equals("")) {
            return 0;
        }

        int left = 0;
        int right = 0;
        int longest = 0;

        char[] cs = s.toCharArray();
        for (int i = 0; i < cs.length; i++) {
            if (cs[i] == '(') {
                left += 1;
            } else {
                right += 1;
            }
            if (left == right) {
                longest = Math.max(left * 2, longest);
            } else if (right > left) {
                left = right = 0;
            }
        }

        left = right = 0;
        for (int i = cs.length - 1; i >= 0; i--) {
            if (cs[i] == '(') {
                left += 1;
            } else {
                right += 1;
            }

            if (left == right) {
                longest = Math.max(left * 2, longest);
            } else if (left > right) {
                left = right = 0;
            }

        }
        return longest;
    }
}
